package com.leetcode.www;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
 *
 * User:yxd
 * Date:2022-04-11
 * Time:0:07
 */
public class Array204 {
    public int countPrimes(int n) {
        List<Integer> primes = new ArrayList<Integer>();
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                primes.add(i);
            }
            for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) {//也是将所有的倍数都变为0,就不是质数了
                isPrime[i * primes.get(j)] = 0;//也是将所有的倍数
                if (i % primes.get(j) == 0) {//等于0的话,就表示这个数的倍数已经全部置为0了,不需要再一次进行操作了
                    break;
                }
            }
        }
        return primes.size();
    }
    public int countPrimes1(int n) {
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);//填充1
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                ans += 1;
                if ((long) i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;//将i所有的倍数都置为0,后面再加的时候就不会再有这个数锁造成的非质数
                    }
                }
            }
        }
        return ans;
    }
    public int countPrimes2(int n) {//这种会超出时间限制
        if(n == 0 || n == 1 || n == 2)return 0;
        int count = 0;
        for(int i = 2;i < n;i ++){
            if(isT(i)){
                count ++;
            }
        }
        return count;
    }
    public boolean isT(int x){

        for(int i = 2;i * i <= x;i ++){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }
}
